#include <stdio.h>
#include <string.h>

// 冒泡排序
void bubblesort(int R[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) { // 外层循环控制遍历次数
        for (j = 0; j < n - 1 - i; j++) { // 内层循环进行相邻元素比较
            if (R[j] > R[j + 1]) { // 如果前一个元素大于后一个元素，则交换
                int temp = R[j];
                R[j] = R[j + 1];
                R[j + 1] = temp;
            }
        }
    }
}


// 改进的冒泡排序
void bubblesort_improved(int R[], int n) {
    int i, j, flag = 0;  // i为执行趟数；j为该趟内的循环比较下标，flag标识每趟中是否发生交换
    int temp;  // 交换的中间变量
    for (i = 0; i < n; i++) { // 执行趟数
        flag = 0;  // 每趟开始前重置flag
        for (j = 0; j < n - i - 1; j++) { // 每趟比较从0开始到n-i-1为止
            if (R[j] > R[j + 1]) { // 相邻比较，逆序则交换
                temp = R[j];
                R[j] = R[j + 1];
                R[j + 1] = temp;
                flag = 1;  // 如果发生交换 flag=1
            }
        }
        if (flag == 0) {  // 如果整趟都没发生交换，说明已基本有序，无须继续排序
            break;
        }
    }
}

// 打印数组
void PrintArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 检查数组是否已排序
int IsSorted(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        if (arr[i] < arr[i-1]) {
            return 0;  // 未排序
        }
    }
    return 1;  // 已排序
}

// 复制数组
void CopyArray(int src[], int dest[], int n) {
    for (int i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

// 测试单个数组的两种排序方法
void TestBothSorts(int original[], int n, const char* testName) {
    int arr1[n], arr2[n];
    
    printf("=== %s ===\n", testName);
    printf("原始数组: ");
    PrintArray(original, n);
    
    // 测试基础冒泡排序
    CopyArray(original, arr1, n);
    bubblesort(arr1, n);
    printf("基础冒泡排序结果: ");
    PrintArray(arr1, n);
    printf("基础版本排序正确性: %s\n", IsSorted(arr1, n) ? "✓ 正确" : "✗ 错误");
    
    // 测试改进冒泡排序
    CopyArray(original, arr2, n);
    bubblesort_improved(arr2, n);
    printf("改进冒泡排序结果: ");
    PrintArray(arr2, n);
    printf("改进版本排序正确性: %s\n", IsSorted(arr2, n) ? "✓ 正确" : "✗ 错误");
    
    printf("\n");
}

// 主测试函数
void TestBubbleSorts() {
    printf("========== 冒泡排序对比测试 ==========\n\n");
    
    // 测试用例1：一般情况
    int test1[] = {64, 34, 25, 12, 22, 11, 90};
    int n1 = sizeof(test1) / sizeof(test1[0]);
    TestBothSorts(test1, n1, "测试1：一般情况");
    
    // 测试用例2：已排序数组（最佳情况）
    int test2[] = {1, 2, 3, 4, 5, 6, 7};
    int n2 = sizeof(test2) / sizeof(test2[0]);
    TestBothSorts(test2, n2, "测试2：已排序数组（最佳情况）");
    
    // 测试用例3：逆序数组（最坏情况）
    int test3[] = {7, 6, 5, 4, 3, 2, 1};
    int n3 = sizeof(test3) / sizeof(test3[0]);
    TestBothSorts(test3, n3, "测试3：逆序数组（最坏情况）");
    
    // 测试用例4：基本有序（部分逆序）
    int test4[] = {1, 2, 3, 5, 4, 6, 7};
    int n4 = sizeof(test4) / sizeof(test4[0]);
    TestBothSorts(test4, n4, "测试4：基本有序");
    
    // 测试用例5：重复元素
    int test5[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    int n5 = sizeof(test5) / sizeof(test5[0]);
    TestBothSorts(test5, n5, "测试5：重复元素");
    
    // 测试用例6：单个元素
    int test6[] = {42};
    int n6 = sizeof(test6) / sizeof(test6[0]);
    TestBothSorts(test6, n6, "测试6：单个元素");
    
}

// 主函数
int main() {
    TestBubbleSorts();
    return 0;
}
